#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
} node;

// 创建一个空链表
node *list_Create()
{
    node *head;
    head = (node *)malloc(sizeof(node));
    // 判断是否分配成功
    if (head == NULL)
    {
        printf("malloc failed\n");
    }
    // 头结点不用来存储数据
    head->data = 0;
    head->next = NULL;
    return head;
}

// 尾插  失败：-1
int list_tail_insert(node *H, int value)
{
    // 链表是否存在
    if (H == NULL)
    {
        printf("list is error\n"); // 链表不存在
        return -1;
    }
    // 创建一个新结点
    node *newnode = (node *)malloc(sizeof(node));
    if (newnode == NULL)
    {
        printf("newnode malloc faild\n"); // 新结点创建失败
        return -1;
    }
    // 将新数据给新结点
    newnode->data = value;
    newnode->next = NULL;

    // 找到尾结点
    node *p_head = H;
    while (p_head->next != NULL)
    {
        p_head = p_head->next;
    }
    // 此时p_head指向尾结点
    p_head->next = newnode;
    return 0;
}
int show_list(node *H)
{
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if (H->next == NULL)
    {
        printf("list is null\n");
        return -1;
    }
    node *p = H->next;
    while (p != NULL)
    {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
    return 0;
}
int find_node(node *H, int newdata)
{
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if (H->next == NULL)
    {
        printf("list is empty\n");
        return -1;
    }
    node *p;
    p = H->next;//头结点的下一个
    while (p != NULL)
    {
        if (p->data != newdata)
        {
            p = p->next;
        }
        else
        {
            return 1;
        }
    }
    return 0;
}
node *merge(node *list1,node *list2)
{
    int flag;
    if(list1==NULL ||list2==NULL)
    {
        printf("list is error\n");
        return NULL;
    }
    if(list1->next==NULL&&list2->next==NULL)
    {
       printf("list is empty\n");
       return NULL;
    }
    if(list1->next==NULL)
    {
        return list2;
    }
    if(list2->next==NULL)
    {
        return list1;
    }
    node *p2;

    p2=list2->next;
    while(p2!=NULL)
    {
        flag=find_node(list1,p2->data);
        if(flag==0)//没找到
        {
           list_tail_insert(list1,p2->data);
        }
        p2=p2->next;
    }
    return list1;
}
int sort_list(node *list)
{
    int temp;
    node *p=list->next,*q;
    while(p->next!=NULL)
    {
        q=list->next;
        while(q->next!=NULL)
        {
            if(q->data>q->next->data)
            {
                temp=q->data;
                q->data=q->next->data;
                q->next->data=temp;
            }
            q=q->next;
        }
        p=p->next;
    }
}
int main(int argc, char const *argv[])
{
    node *list1 = list_Create(list1);
    node *list2 = list_Create(list2);
    list_tail_insert(list1, 1);
    list_tail_insert(list1, 3);
    list_tail_insert(list1, 5);
    list_tail_insert(list1, 6);
    list_tail_insert(list1, 8);
    printf("list1:\n");
    show_list(list1);

    list_tail_insert(list2, 0);
    list_tail_insert(list2, 2);
    list_tail_insert(list2, 3);
    list_tail_insert(list2, 5);
    list_tail_insert(list2, 9);
    printf("list2\n");
    show_list(list2);

    printf("合并后:\n");
    list1=merge(list1,list2);
    show_list(list1);

    printf("排序后:\n");
    sort_list(list1);
    show_list(list1);

    return 0;
}
